This application claims the priority benefit of Taiwan application serial no. 89100598, filed Jan. 15, 2000.
1. Field of Invention
The present invention relates to an Ethernet switch. More particularly, the present invention relates to the relay control of an Ethernet switch that enlists a hashing function method to increase hit rate and network transmission efficiency.
2. Description of Related Art
Although Ethernet is the most popular local area network, a transmission rate of 10 Mbps (bit per second) is not enough for multimedia communication. Consequently, an improved solution, Fast Ethernet, which has a transmission rate of 100 Mbps, is developed. However, in fast Ethernet an additional convergence sublayer (CS) must be introduced between the media access control (MAC) sublayer and the physical medium dependent (PMD) sublayer. Hence, the network interface card must be updated by a fast Ethernet interface card. However, in the case of increasing the transmission rate without updating the original slow network interface card in each network station, an Ethernet switch structure is preferred.
In the conventional Ethernet, a twisted wires is used as a medium for network connection. It does not matter if the transmission rate is 10 Mbps or 100 Mbps, workstations and server are linked together through an Ethernet hub so that network data are shared. In general, bandwidth of the hub is shared by the linked workstations attached to the network. For example, for a 100 Mbps Ethernet hub with 16 ports, if 4 ports are connected to workstations, network bandwidth is shared by the 4 workstations. If 16 ports are connected to workstations, network bandwidth is shared by the 16 workstations. As the number of network users increases, network collision will become more serious and bandwidth assigned to each user will be narrower as well. Hence, conventional Ethernet hub is no longer capable of satisfying the demands of users.
An Ethernet switch is developed for improving network bandwidth. The Ethernet switch permits the simultaneous data transmission of several connected workstations so that overall performance of the network is increased. To achieve the switching function, the Ethernet switch must know which port a workstation is connected to. In other words, the Ethernet switch must have an address learning function similar to a bridge device. When the switch receives a frame signal, a routing table will be consulted to lookup for the port connected to the destination workstation. If the port is found, a control processor will send out a control signal to a switching element so that the frame signal is output to the port. Conversely, if the port is not found in the routing table, the frame signal will be broadcast to every connected port so that the destination workstation is sure to receive the frame.
Assume that N is the number of connection ports in an Ethernet switch, the switch is capable of transmitting frame signal to a maximum of N/2 workstations. For example, a 16 ports 100 Mbps Ethernet switch can have a maximum network bandwidth of 800 Mbps if collisions are ignored. On the other hand, a 16 ports 100 Mbps Ethernet hub can have a maximum network bandwidth of just 100 Mbps. Hence, there is a tremendous improvement in transmission capability for the Ethernet.
The Ethernet switch device has a relay control circuit. The relay control circuit is connected to an address table of an external memory. When one port of the Ethernet switch picks up a frame signal, the relay control circuit will search the address table for destination port of the frame signal. If a destination port that corresponds to frame""s destination medium access control (DMAC) address is found in the address table, the frame is sent to the destination port by the relay control circuit. If a destination port that corresponds to the DMAC address is not found in the address table, the frame is broadcast so that the frame signal is received by the destination port. The destination port that corresponds to the DMAC address is identified and written into the address table. However, this will downgrade the performance of the Ethernet switch. In addition, the relay control circuit of the Ethernet switch also has a frame-filtering function. In general, the address table of an Ethernet switch is stored in a memory. For cost down, the memory is usually a static random access memory (SRAM). Due to the rapid expansion of computer network, the address table within the SRAM can no longer hold all the network addresses of all Ethernet workstations. Hence. it is important to choose a suitable lookup method for obtaining the destination port corresponding to a DMAC address as soon as possible.
At present, performance of an Ethernet switch depends very much on time consumed on finding out the destination port from a frame""s DMAC address and transmitting the frame. Currently, various lookup methods capable of shortening lookup time have been implemented in the relay control circuit of the Ethernet switch.
The most common lookup method includes the linear lookup, binary tree lookup and hash function lookup. In the linear lookup method, the DMAC address is compared with the content in an address table one by one from the very beginning to the end. Due to relative inefficiency, linear lookup method is rarely used now. In the binary tree lookup method, checking area is cut in half with each level down the tree. Therefore, the binary tree method converges upon the required address much faster than the linear lookup method. However, the binary lookup method is still not satisfied in Ethernet switch.
In hashing function lookup method, DMAC addresses are sorted on a fix-sized table. A mathematical function h is used to represent the address location of the destination address x in the table. Hence, h(x) represent the address of x in the table. This h(x) is called a hashed address or a home address of x. Assume that the memory addresses for storing a DMAC ADDRESS table are contiguous, the memory addresses form a hash table (ht). The hash table is divided into b buckets from ht[0] to ht[bxe2x88x921]. Each bucket has s recording stores. In other words, each bucket has s slots, each capable of holding a record. In general, s=1, and hence each bucket contains a record. The hashing function h(x) performs a transformation of the destination medium access control (DMAC) address x so that a group of possible DMAC addresses is assigned to one of the integer between 0 and bxe2x88x921.
In general, the number of DMAC addresses will be greater than the number of buckets used in the hashing table. Therefore, the hashing function h(x) matchs a few different DMAC addresses to the same bucket. For DMAC addresses I1 and I2 with h(I1)=h(I2), they are referred to as synonyms. As long as there are still vacant slots within a bucket, the synonyms are placed in different slots inside the same bucket. When a bucket is already full, any attempt at putting a new DMAC address into the bucket will result in an overflow. On the other hand, any attempt at forcing two different nonsynonymous address into one bucket will result in a collision.
A conventional relay control circuit of an Ethernet switch usually truncates 48 bits DMAC address into a shorter length such as 11 bits. The 11 bits data are sent to the memory for a table lookup operation. Since no hashing function h(x) or other processing methods are used, hit rate of the table lookup operation is rather low. If there is no hit in a table lookup operation, the relay control circuit has to broadcast the DMAC address again. When a destination port that corresponds to the DMAC address is found, the destination port and the address is written back to the table inside the memory. However, this will degrade the performance of the network.
Accordingly, one object of the present invention is to provide a relay control circuit and its method of operation that utilizes a hashing function algorithm to increase the hit rate in a table lookup operation.
In according with the foregoing and other objectives, the present invention provides a relay control circuit which is installed inside a switch device. The switch device has an address/port table, and receives a frame signal with a destination medium access control (DMAC) address. The relay control circuit comprises an address scrambling circuit and a transformation circuit. The address scrambling circuit scrambles the DMAC address of the frame signal. The transformation circuit is coupled to the address scrambling circuit, and generates an index address according to the scrambled DMAC address. The switch device sends out the frame signal according to the index address and the address/port table. In the embodiment of this invention, the transformation circuit includes a cyclic redundancy checking circuit.
The present invention also provides a switch device which is capable to receive and send out a frame. The switch device comprises an address acquisition circuit, a memory unit, and a relay control circuit. The address acquisition circuit obtains a destination medium access control (DMAC) address from the received frame. An address table is stored in the memory unit. The relay control circuit is coupled to the address acquisition circuit and the memory unit. The relay control circuit scrambles the DMAC address to generate a scrambled DMAC address. The scrambled DMAC address is transformed into an index address by the relay control circuit. Finally, the frame is sent out according to the index address and the address table.
In according with the foregoing and other objectives, the present invention provides a relay control method which sends out a frame signal in a switch network with an address/port table. The frame signal has a DMAC address. The relay control method includes scrambling the DMAC address of the frame signal, and then transforming the scrambled DMAC address into an index with hash function. The frame signal is sent out according to the index and the address/port table. In the embodiment of this invention, the scrambled DMAC address is transformed into the index by performing a CRC operation.
The method involves changing the byte order 1, 2, 3, 4, 5 and 6 of a 48-bits DMAC address obtained from a network frame to the byte order 1, 2, 3, 5, 6 and 4. The re-arranged bytes then passes through a cyclic redundancy checking (CRC) circuit for a cyclic redundancy checking and the generation of an 11-bits remainder. The 11-bits remainder is sent to the memory to perform a table lookup. The method is capable of obtaining the address of a connection port that corresponds to the destination address in a very short time so that the frame can be relayed immediately. Hence, the switching rate of the relay control circuit inside an Ethernet switch is increased.
In the embodiment of this invention, bit length of the DMAC address data obtained by the relay control circuit from the address acquisition circuit need not be the full DMAC address data length. The DMAC address data length can be truncated to obtain a shorter DMAC address data and then the truncated data can be sent to the cyclic redundancy checking circuit for cyclic redundancy checking. Furthermore, the number of bits in the remainder produced by the cyclic redundancy checking circuit need not be limited to 11. In fact, remainder bits produced by any other cyclic redundancy checking circuit or the truncated remainder bits from any cyclic redundancy checking circuit should also be within the scope of this invention.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.